In the prior art, it has been well known that computer systems can be used to encode digital values in order to reduce storage requirements. There are many techniques for encoding digital values.
For values which are arranged sequentially, for example, in an ascending order, the differences between successive values can be encoded. This is called delta value encoding. For delta encoding to be effective, small delta values should be stored in a small number of bytes. Having variable length delta encodings makes the decoding more complex, since the end of each decoding must be detected.
Another problem with delta value encoding is that in order to decode any given value, all previous values must be decoded. This can consume a large number of processor cycles. The number of cycles consumed can be very large if the number of delta values to be decoded is in the hundreds of millions.
This situation can exists in an index to a unique distributed database which has recently emerged in the form of the World-Wide-Web (Web). The database records of the Web are in the form of pages accessible via the Internet. Here, tens of millions of pages are accessible by anyone having a communications link to the Internet. Each page can include many thousands of words.
A full word index to the Web pages may have many pointers to words of the pages. For example, the word "the" appears at well over 300,000,000 different locations. If the pointers are maintained sequentially, then the pointers can be delta encoded.
A procedure of ten instructions which takes 10 cycles to decode a delta value will be twice as fast as a procedure which requires 20 cycles. For the decoding of millions of delta values per second, eliminating even a single instruction from the procedure will have a significant payback.
Therefore it is desired to prove a delta encoding which minimizes storage and decoding time.